package com.lwl.Algorithmic_data_structure.class27KMP;

/**
 * @author lwl
 * @Description KMP：字符串的匹配算法
 * @date 2023/6/26 12:02
 */
public class Code01KMP {

    public static int getIndexOf(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return -1;
        }
        int index1 = 0;
        int index2 = 0;
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] nextArray = createNextArray(s2);
        while (index1 < str1.length && index2 < str2.length) {
            if (str1[index1] == str2[index2]) {
                index1++;
                index2++;
            } else if (nextArray[index2] == -1) {
                index1++;
            } else {
                index2 = nextArray[index2];
            }
        }
        return index2 == str2.length ? index1 - index2 : -1;
    }

    private static int[] createNextArray(String s) {
        char[] str = s.toCharArray();
        int[] next = new int[s.length()];
        next[0] = -1;
        next[1] = 0;
        int index = 2;
        int samePrefixIndex = 0;
        while (index < str.length) {
            if (str[samePrefixIndex] == str[index - 1]) {
                next[index] = next[samePrefixIndex + 1];
                index++;
            } else if (samePrefixIndex > 0) {
                samePrefixIndex = next[samePrefixIndex];
            } else {
                next[index] = 0;
                index++;
            }
        }
        return next;
    }

    // 利用bfprt算法求解，是O(N)的过程
    public static int getMinKthByBFPTR(int[] arr, int K) {
        return select(arr, 0, arr.length - 1, K - 1);
    }

    public static int select(int[] arr, int begin, int end, int k) {
        if (begin == end) {//数组中只有一个数时，直接返回
            return arr[begin];
        }
        int pivot = medianOfMedians(arr, begin, end);//求出以哪个数作为划分值
        int[] pivotRange = partition(arr, begin, end, pivot);//注意，进行完partation过程后，arr数组已经不是无序的了
        if (k >= pivotRange[0] && k <= pivotRange[1]) {
            return arr[k];//如果需要求的数正好在等于区域，直接返回arr[k]
        } else if (k < pivotRange[0]) {//此时我们要找的数比divide小，递归求前半部分
            return select(arr, begin, pivotRange[0] - 1, k);
        } else {//此时我们要找的数比divide大，递归求后半部分
            return select(arr, pivotRange[1] + 1, end, k);
        }
    }

    //这个函数是将root数组star位置到finish位置分成每5个数一个小组，并求出每个小组内的中位数
    public static int medianOfMedians(int[] arr, int begin, int end) {
        int num = end - begin + 1;//求出长度
        int offset = num % 5 == 0 ? 0 : 1;//最后如果剩余的数不足5个，我们也将其分成一个小组，和前面同等对待
        int[] mArr = new int[num / 5 + offset];//这个数组存的是每个小组内的中位数
        for (int i = 0; i < mArr.length; i++) {//依次往median数组中填数
            int beginI = begin + i * 5;//第i组数对应root数组上的位置
            int endI = beginI + 4;
            mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
        }
        //求出生成好的median数组的中位数，作为partation函数的划分值
        return select(mArr, 0, mArr.length - 1, mArr.length / 2);
    }

    //这个函数求的是在root数组中beginI位置到endI位置上的中位数（其实就是求由每5个数所分成的小组的小组内的中位数）
    public static int getMedian(int[] arr, int begin, int end) {
        //插入排序
        insertionSort(arr, begin, end);
        int sum = end + begin;
        int mid = (sum / 2) + (sum % 2);//这个地方加上sum%2是为了确保偶数个数时我们求的是中间两个数的后一个
        return arr[mid];
    }

    public static void insertionSort(int[] arr, int begin, int end) {
        for (int i = begin + 1; i != end + 1; i++) {
            for (int j = i; j != begin; j--) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    //partation函数求的是等于pivotValue的范围, 在 arr【range[0]~range[1]】 中 都是 等于 pivotValue
    //同时也会把数组按pivotValue 分成左右两部分
    public static int[] partition(int[] arr, int begin, int end, int pivotValue) {
        int small = begin - 1;//这么设值是为了应对整个数组都是比pivotValue大的情况，尽管概率很小
        int cur = begin;
        int big = end + 1;//这么设值是为了应对整个数组都是比pivotValue小的情况，尽管概率很小
        while (cur != big) {
            if (arr[cur] < pivotValue) {
                swap(arr, ++small, cur++);
            } else if (arr[cur] > pivotValue) {
                swap(arr, cur, --big);
            } else {
                cur++;
            }
        }
        int[] range = new int[2];
        range[0] = small + 1;
        range[1] = big - 1;
        return range;
    }

    public static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}
